#include<cstdio>//uncle-lu
#include<algorithm>
template<class T>void read(T &x)
{
	x=0;int f=0;char ch=getchar();
	while(ch<'0'||ch>'9') { f|=(ch=='-'); ch=getchar(); }
	while(ch<='9'&&ch>='0') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }
	x = f ? -x : x;
	return ;
}

int t, k;

long long int f(int x)
{
	long long int sum = 1;
	for (int i = 1; i <= x; i++) 
		sum *= i;
	return sum;
}

int c(int n, int m)
{
	return f(n)/(f(m)*f(n-m));
}

void func(int n, int m)
{
	long long int ans = 0;
	for (int i = 0; i <= n; i++) 
		for (int j = 0; j <= std::min(i,m); j++) 
			if(c(i,j) % k == 0)
				ans++;

	printf("%lld\n", ans);
	return ;
}

int main()
{
	int n, m;
	read(t);read(k);
	for (int i = 1; i <= t; i++) 
	{
		read(n);read(m);
		func(n, m);
	}
	
	return 0;
}
